﻿#include "Sort.h"
#include "Stack.h"
void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

// 插入排序
void InsertSort(int* a, int n)
{
	assert(a);

	for (int i = 0; i < n - 1; ++i)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
	
}


// 希尔排序时间复杂度为 O(N^1.3-N^2)
void ShellSort(int* a, int n)
{

	assert(a);
	int gap=n;
	//gap>1相当于预处理，让数组接近有序
	//gap==1相当于直接插入排序，保证数组有序
	while (gap > 1)
	{
		gap = gap / 3 + 1;//加一是保证最后一次gap一定是1
		//gap==1最后一次就相当于直接插入排序
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;

			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
				a[end + gap] = tmp;
			}
		}

	}
}

void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}

void SelectSort(int* a, int n)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		int max = begin;
		int min = begin;
		for (int i = begin+1; i <= end; i++)
		{
			if (a[max] < a[i])
			{
				max = i;
			}
			if (a[min] > a[i])
			{
				min = i;
			} 
		}
		Swap(&a[begin], &a[min]);
		//如果max和begin位置重叠，则max的位置需要修改
		if (max == begin)
		{
			max = min;
		}
		Swap(&a[end], &a[max]);

		begin++;
		end--;
	}
}


// 堆排序
//正确的总时间复杂度
//建堆阶段：O(n)
//排序阶段：O(n log n)
//总时间复杂度：O(n) + O(n log n) = O(n log n)
void AdjustDwon(int* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i++)
	{
		AdjustDwon(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
		end--;
	}
}

// 冒泡排序
void BubbleSort(int* a, int n)
{
	int end = n;
	while (end>0)
	{
		int exchange = 0;
		for (int i = 1; i < end; i++)
		{
			if (a[i - 1] > a[i])
			{ 
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
			if (exchange == 0)
			{
				break;
			}
		}
		end--;
	}
}

//如果不使用三数选中，快排在处理有序数组时会产生栈溢出的报错，因为栈的空间有限而如果
//数组是有序的每一次都选最后一个作为key，会导致每一次递归有序数组中，若基准选择不当（如固定选首元素），每次分区后：
//左子数组为空，右子数组为 n−1 个元素。
//递归调用栈的深度为 n（例如，对升序数组[1, 2, 3, ..., n]，每次递归仅减少一个元素）。
//栈空间限制：递归深度超过系统栈容量时，栈溢出。
//保证不要选到最大或者最小，让有序时变成最优
int GetMidIndex(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
			return mid;
		else if(a[begin]>a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
	else
	{
		if (a[mid] > a[end])
			return mid;
		else if (a[begin] < a[end])
			return begin;
		else
			return end;
	}
}

// 快速排序hoare版本
//左右指针法
int PartSort1(int* a, int begin, int end)
{
	//让最坏的情况不在出现
	//时间复杂度不在看最坏的情况了，综合而言快排的复杂度为O(N*logN)
	int MidIndex = GetMidIndex(a, begin, end);
	Swap(&a[MidIndex], &a[end]);
	int keyindex = end;
	while (begin < end)
	{
		while (begin < end && a[begin] <= a[keyindex])
		{
			begin++;
		}
		while (begin < end && a[end] >= a[keyindex])
		{
			end--;
		}
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[keyindex]);
	return begin;
}


//挖坑法
int PartSort2(int* a, int begin, int end)
{
	int MidIndex = GetMidIndex(a, begin, end);
	Swap(&a[MidIndex], &a[end]);
	int key = a[end];
	while (begin < end)
	{
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[end] = a[begin];
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		a[begin] = a[end];
	}
	a[begin] = key;
	return begin;
}

//前后指针法
int PartSort3(int* a, int begin, int end)
{
	int MidIndex = GetMidIndex(a, begin, end);
	Swap(&a[MidIndex], &a[end]);
	int cur = begin;
	int prev = begin - 1;
	int key = a[end];
	while (cur<end)
	{
		if (a[cur] < key )
		{
			prev++;
			if (prev != cur)  // 避免不必要的交换
			{
				Swap(&a[cur], &a[prev]);
			}
		}
			cur++;

	}
	prev++;
	Swap(&a[prev],&key);
	return prev;
}

//未优化 
//void QuickSort(int* a, int left, int right)
//{
//	assert(a);
//	if (left >= right)
//		return ;
//	int div = PartSort3(a, left, right);
//	//看递归的过程
//	/*PrintArray(a + left, right - left + 1);
//	printf("[%d,%d]%d[%d,%d]", left, div - 1, div, div + 1, right);*/
//	QuickSort(a, left, div - 1);
//	QuickSort(a, div + 1, right);
//}

//优化 当数组小于10个时就没有必要在用递归了
void QuickSort(int* a, int left, int right)
{
	assert(a);
	if (left >= right)
		return;
	if ((right - left + 1) > 10)
	{
		int div = PartSort3(a, left, right);
		//看递归的过程
		/*PrintArray(a + left, right - left + 1);
		printf("[%d,%d]%d[%d,%d]", left, div - 1, div, div + 1, right);*/
		QuickSort(a, left, div - 1);
		QuickSort(a, div + 1, right);
	}
	else
	{
		//小于10个以内的就不用递归了用插入会比较快（已经接近有序了）
		//要排序的是left到right所以开始位置是a+left
		InsertSort(a + left, (right - left + 1));//right-left+1是因为0-9是10个数而9-0=9所以要加一才是10个数了
	}
}


// 快速排序 非递归实现 使用栈来实现
void QuickSortNonR(int* a, int left, int right)
{
	Stack st;
	StackInit(&st);
	StackPush(&st, right);
	StackPush(&st, left);
	while (!StackEmpty(&st))
	{
		int begin = StackTop(&st);
		StackPop(&st);
		int end = StackTop(&st);
		StackPop(&st);
		if ((end - begin + 1) > 10)
		{
			int div = PartSort1(a, begin, end);
			//证明[div+1,end]之间还有两个以上的数还要排，
			//如果end=div+1就证明只有一个数了就不需要排序了
			if (end > div + 1)
			{
				StackPush(&st, end);
				StackPush(&st, div + 1);
			}

			if (begin < div - 1)
			{
				StackPush(&st, div - 1);
				StackPush(&st, begin);
			}
		}
		else
		{
			InsertSort(a + begin, (end - begin + 1));
		}
	}

	StackDestory(&st);
}

void MergeArr(int* a, int start1, int end1, int start2, int end2, int* tmp)
{
	int left = start1, right = end2;
	int tmpIndex = start1;
	while (start1 <= end1&&start2 <= end2)
	{
		if (a[start1] < a[start2])
		{
			tmp[tmpIndex] = a[start1];
			start1++;
			tmpIndex++;
		}
		else
		{
			tmp[tmpIndex] = a[start2];
			start2++;
			tmpIndex++;
		}
	}
	while (start1 <= end1)
	{
		tmp[tmpIndex] = a[start1];
		start1++;
		tmpIndex++;
	}
	while (start2 <= end2)
	{
		tmp[tmpIndex] = a[start2];
		start2++;
		tmpIndex++;
	}
	for (int i = left; i <= right; i++)
	{
		a[i] = tmp[i];
	}
}


void PartMergeSort(int* a, int left,int right, int* tmp)
{
	if (left >= right)
		return;
	int Mid = (left+right) / 2;
	
	PartMergeSort(a, left, Mid, tmp);
	PartMergeSort(a, Mid + 1, right, tmp);

	MergeArr(a, left, Mid, Mid + 1, right,tmp);
}


// 归并排序递归实现
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n);

	PartMergeSort(a, 0, n - 1, tmp);
	free(tmp);
}

// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)*n); 
	int gap = 1;
	while (gap < n )
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + gap * 2 - 1;
			//1 合并时只有一组，第二组不存在，就不需要合并
			if (begin2 > n)
				break;
			//2 合并时第二组只有部分数据，需要修正end2的边界
			if (end2 >= n)
				end2 = n - 1;
			MergeArr(a, begin1, end1, begin2, end2, tmp);
		}
		PrintArray(a, n);     
		gap *= 2;
	}
} 

// 计数排序
void CountSort(int* a, int n)
{
	int min = a[0];
	int max = a[0];
	for (int i = 1; i < n; i++)
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}
	int range = max - min + 1;
	int* CountArr = (int*)malloc(sizeof(int)*range);
	memset(CountArr, 0, sizeof(int)*range);

	//统计次数
	for (int i = 0; i < n; i++)
	{
		CountArr[a[i] - min]++;
	}

	//排序
	int Arrindex = 0;
	for (int i = 0; i < range; i++)
	{
		while (CountArr[i])
		{
			a[Arrindex] = i + min;
			Arrindex++;
			CountArr[i]--;
		}
	}
	free(CountArr);
}

//二分查找
int Binarysearch(int* a, int n, int x, int* Location) {
	int num = 0;
	int start = 0;
	int end = n - 1;
	while (start <= end) 
	{  
		num++;
		int mid = start + (end - start) / 2;  
		if (a[mid] == x)
		{
			*Location = mid;
			return num;
		}
		if (a[mid] > x) 
			end = mid - 1;
		else 
			start = mid + 1; 
	}
	
	printf("查找失败\n");
	return -1;
}






